#include <bits/stdc++.h>
using namespace std;

const int N = 1e4;
class Solution
{
  public:
    int mem[N][N];
    int dfs(int x, int y, int &m, int &n)
    {
        if (x == m - 1 || y == n - 1)
            return 1;
        if (mem[x][y])
            return mem[x][y];
        return mem[x][y] = dfs(x + 1, y, m, n) + dfs(x, y + 1, m, n);
    }
    int uniquePaths(int m, int n)
    {
        //return dfs(0, 0, m, n);
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 1));
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};